package offerbook;

/**
 * Created at 2019/10/28 0028 下午 6:02
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
 * 输入一个数组,求出这个数组中的逆序对的总数P。
 * 并将P对1000000007取模的结果输出。 即输出P%1000000007
 */
public class Code36_InversePairsInArray {

    /**
     * 时间没有通过
     */
    public static int inversePairs(int []arr){
        if(arr == null || arr.length <=1){
            return 0;
        }
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j <arr.length ; j++) {
                if( arr[i] > arr[j]){
                   sum ++;
                }
            }
        }
        return sum;
    }

    /**
     * 通过75%,要把每个sum都%1000000007，就通过100%
     */
    public static int inversePairs1(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    private static int process(int[] arr, int left, int right) {
        if( left==right ){
            return 0;
        }
        int mid = (left+right) >> 1;

        return process(arr,left,mid)
                + process(arr,mid+1,right)
                +merge2(arr,left,mid,right);

    }

    /**
     * 从大到小排序
     */
    private static int merge1(int[] arr, int left, int mid, int right) {
        int []help = new int[right-left+1];
        int p1 = left;
        int p2 = mid + 1;
        int index = 0;
        int sum = 0;
        while (p1 <= mid && p2 <= right) {
            //如果左侧的p1位置比p2位置大，那么p1-mid比p2都大
            sum += arr[p1] > arr[p2] ? (mid - p1 + 1) : 0;
            //从大到小排序
            help[index++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
        }
        while (p1 <= mid) {
            help[index++] = arr[p1++];
        }
        while (p2 <= right) {
            help[index++] = arr[p2++];
        }
        index = 0;
        for (int i = left; i <= right; i++) {
            arr[i] = help[index++];
        }
        return sum;
    }

    /**
     * 从小到大排序
     */
    private static int merge2(int[] arr, int left, int mid, int right) {
        int []help = new int[right-left+1];
        int p1 = left;
        int p2 = mid + 1;
        int index = 0;
        int sum = 0;
        while (p1 <= mid && p2 <= right) {
            //如果p1比p2大，那么p1 - mid 都别p2大
            sum += arr[p1] > arr[p2] ? (mid - p1 +1) : 0;
            //从小到大排序
            help[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[index++] = arr[p1++];
        }
        while (p2 <= right) {
            help[index++] = arr[p2++];
        }
        index = 0;
        for (int i = left; i <= right; i++) {
            arr[i] = help[index++];
        }
        return sum;
    }
    public static void main(String[] args) {
        int [] arr = {1,7,9,5,2,6,8,0};
        System.out.println(inversePairs(arr));
        System.out.println(inversePairs1(arr));
    }
}
